import java.util.*;

public class Change {
    public static void main(String[] args) {
        System.out.println("请输入中继表达式:");
        Scanner sc = new Scanner(System.in);
        String expression = sc.nextLine();
        String changedExpression=changedWay(expression);
        System.out.println(changedExpression);
    }

    /*
    1.遇到操作数：直接输出（添加到后缀表达式中）
    2.栈为空时，遇到运算符，直接入栈
    3.遇到左括号：将其入栈
    4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，括号不输出。
    5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
    6.最终将栈中的元素依次出栈，输出。
     */

    public static String changedWay(String expression) {
        String changedExpression = "";
        Stack signStack = new Stack();// 操作符栈
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c >= '0' && c <= '9') {
                changedExpression=changedExpression+" "+c;
            }
            else if (signStack.empty()) {
                signStack.push(c);
            }
            else if (c == '+' || c == '-' || c == '*' || c == '/') {
                changedExpression=changedExpression+" ";
                if (judgeValue(c) >= judgeValue((Character) signStack.peek())) {//优先级高于或等于，运算符号均进栈
                    signStack.push(c);
                }
                else {
                    changedExpression=changedExpression+(char)signStack.pop();
                    signStack.push(c);
                }
            }
        }
        while(!signStack.empty()){
            changedExpression=changedExpression+" "+String.valueOf(signStack.pop());
        }
        return changedExpression;
    }

    private static int judgeValue(char c) {
        int value = 0;
        switch (c) {
            case '(':
                value = 1;
                break;
            case '+':
            case '-':
                value = 2;
                break;
            case '*':
            case '/':
                value = 3;
                break;
            case ')':
                value = 4;
            default:
                value = 0;
        }
        return value;
    }
}
